package algorithms4g

import "fmt"

func init() {
	l1 := &ListNode{2, nil}
	l2 := &ListNode{3, l1}
	l3 := &ListNode{5, l2}
	l4 := &ListNode{7, l3}
	l5 := &ListNode{8, l4}
	res := reverseListNode(l5)
	s := []int{}
	for res != nil {
		s = append(s, res.Val)
		res = res.Next
	}
	fmt.Println("链表反转-迭代", s)
	s2 := []int{}
	res = reverseListNode2(l1)
	for res != nil {
		s2 = append(s2, res.Val)
		res = res.Next
	}
	fmt.Println("链表反转-递归", s2)
}

/**
链表反转-迭代
*/
func reverseListNode(head *ListNode) *ListNode {
	var prev *ListNode
	prev, curr := nil, head
	for curr != nil {
		next := curr.Next
		curr.Next = prev
		prev = curr
		curr = next
	}
	return prev
}

/**
链表反转-递归
*/
func reverseListNode2(head *ListNode) *ListNode {
	for head == nil || head.Next == nil {
		return head
	}
	newHead := reverseListNode2(head.Next)
	head.Next.Next = head
	head.Next = nil
	return newHead
}
